import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class SolutionOfferII115 {
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n=nums.length;
        int[] first=new int[n+1];
        Arrays.fill(first,-1);
        int[] next=new int[100005];
        int[] go=new int[100005];
        int[] du=new int[n+1];
        boolean[] visit=new boolean[n+1];
        int cur=0;
        for (int[] sequence : sequences) {
            for (int i=0;i<sequence.length-1;i++){
                next[cur]=first[sequence[i]];
                first[sequence[i]]=cur;
                go[cur]=sequence[i+1];
                du[sequence[i+1]]++;
                cur++;
            }
        }
        Queue<Integer> queue=new LinkedList<>();
        for (int num : nums) {
            if (du[num]==0){
                queue.offer(num);
                visit[num]=true;
            }
        }
        while (!queue.isEmpty()){
            if (queue.size()!=1){
                return false;
            }
            int t=queue.poll();
            int p=first[t];
            while (p!=-1){
                int v=go[p];
                du[v]--;
                if (du[v]==0){
                    queue.offer(v);
                    visit[v]=true;
                }
                p=next[p];
            }
        }
        for (int i=1;i<=n;i++) {
            if (!visit[i]){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new SolutionOfferII115().sequenceReconstruction(new int[]{1,2,3},new int[][]{{1,2},{1,3},{2,3}}));
    }
}
